//给你一个整数数组 nums，请你将该数组升序排列。 
//
// 你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,2,3,1]
//输出：[1,2,3,5]
//解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。
// 
//
// 示例 2： 
//
// 
//输入：nums = [5,1,1,2,0,0]
//输出：[0,0,1,1,2,5]
//解释：请注意，nums 的值不一定唯一。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5 * 10⁴ 
// -5 * 10⁴ <= nums[i] <= 5 * 10⁴ 
// 
//
// Related Topics 数组 分治 桶排序 计数排序 基数排序 排序 堆（优先队列） 归并排序 👍 1144 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] sortArray(int[] nums) {
//        //1.插入排序
//        //int low = 1;//插入排序的边界,low开始的数组是未排序的
//        for(int low = 1; low <nums.length; low++){//索引小于low的数据是已排序
//            int insertedNum = nums[low];//待插入的数据
//            int i = low -1;
//            while(i>=0 && nums[i] >insertedNum){
//                nums[i+1] = nums[i];
//                i--;
//            }
//            //找到插入位置
//            if(i != low -1)//i == low -1代表low这个位置不需要移动
//                nums[i+1] = insertedNum;
//        }
//        return nums;
//        运行失败:
//        Time Limit Exceeded
//        测试用例:[110, 100, 0]
//        stdout:

//        //1.希尔排序（分组的插入排序）
//        for(int gap=nums.length>>1; gap >=1; gap=gap>>1){
//            //以下是插入排序，索引i跳动的步长为gap
//            for(int low = gap;low < nums.length; low++){
//                int insertedNum = nums[low];//待插入的数据
//                int i = low -gap;
//                while(i>=0 && nums[i] >insertedNum){
//                    nums[i+gap] = nums[i];
//                    i-=gap;
//                }
//                //找到插入位置
//                if(i != low - gap)
//                    nums[i+gap] = insertedNum;
//            }
//        }
//        return nums;

        //2. 计数排序
        int max =nums[0];
        int min = nums[0];
        for(int i=1; i < nums.length; i++){
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        int [] count = new int[max - min + 1];//count索引从零开始，
        for(int i=0; i< nums.length; i++){
            count[nums[i] - min] ++;
        }
        int index = 0;
        for(int i = 0; i<count.length; i++){
            while(count[i] > 0){
                nums[index++] =i + min;
                count[i]--;
            }
        }
        return nums;

        //单边快排 （随机）
        //双边快排  （随机）
        // 快排（随机、重复）
        // 快排 （随机，重复） + 插入



    }
}
//leetcode submit region end(Prohibit modification and deletion)
